home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Language / Compiler / buildGraphs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-16  |  6.2 KB  |  236 lines
  1. /*
  2.  * @(#)buildGraphs.c    1.3  6/29/87
  3.  */
  4. #include "assert.h"
  5. #include "nodes.h"
  6. #include "map.h"
  7. #include "sequence.h"
  8. #include "trace.h"
  9.  
  10. Map symbolsRead;
  11. Map symbolsWritten;
  12.  
  13. void addAnEdge(map, symref, expression)
  14. Map map;
  15. NodePtr symref, expression;
  16. {
  17.   NodePtr list;
  18.   if (symref->b.symref.symbol == NULL) assert(FALSE);
  19.   list = (NodePtr) Map_Lookup(map, (int)symref->b.symref.symbol);
  20.   if ((int)list == NIL) list = NULL;
  21.   Sequence_Add(&list, expression);
  22.   Map_Insert(map, (int)symref->b.symref.symbol, (int)list);
  23. }
  24.  
  25. static Boolean duplicatesSymbol(p, st)
  26. NodePtr p;
  27. Symbol st;
  28. {
  29.   NodePtr q;
  30.   switch (p->tag) {
  31.     case P_INVOC:
  32.       Sequence_For(q, p->b.invoc.args)
  33.     assert(q->tag == P_ARG);
  34.     q = q->b.arg.exp;
  35.     if (q->tag == P_SYMREF && q->b.symref.symbol == st) {
  36.       TRACE2(graph, 1, "reference to %s on line %d is as arg, so duplicates",
  37.         ST_SymbolName(st), p->lineNumber);
  38.       return(TRUE);
  39.     }
  40.       Sequence_Next
  41.       TRACE2(graph, 1, "Invocation on %s on line %d does not duplicate",
  42.     ST_SymbolName(st), p->lineNumber);
  43.       break;
  44.     case P_ASSIGNSTAT:
  45.       Sequence_For(q, p->b.assignstat.right)
  46.     if (q->tag == P_SYMREF && q->b.symref.symbol == st) {
  47.       TRACE2(graph, 1, "reference to %s on line %d is as expression, so duplicates",
  48.         ST_SymbolName(st), p->lineNumber);
  49.       return(TRUE);
  50.     }
  51.       Sequence_Next
  52.       TRACE2(graph, 1, "Assignment to %s on line %d does not duplicate",
  53.     ST_SymbolName(st), p->lineNumber);
  54.       break;
  55.     case P_ATLIT:
  56.     case P_OBLIT:
  57.       TRACE2(graph, 1, "reference to %s on line %d is as import, so duplicates",
  58.     ST_SymbolName(st), p->lineNumber);
  59.       return(TRUE);
  60.       /* break; */
  61.     default:
  62.       break;
  63.   }
  64.   return(FALSE);
  65. }
  66.  
  67. void buildSymbolGraph(p)
  68. register NodePtr p;
  69. {
  70.   register NodePtr q, list;
  71.   Boolean duplicatesSelf;
  72.   register Symbol st;
  73.  
  74.   if ((int)p <= 0x200) return;
  75.   switch (p->tag) {
  76.     case P_ASSIGNSTAT:
  77.       Sequence_For(q, p->b.assignstat.left)
  78.     assert(q->tag == P_SYMREF);
  79.     addAnEdge(symbolsWritten, q, p);
  80.       Sequence_Next
  81.       Sequence_For(q, p->b.assignstat.right)
  82.     if (q->tag == P_SYMREF) addAnEdge(symbolsRead, q, p);
  83.       Sequence_Next
  84.       break;
  85.     case P_INVOC:
  86.       if (p->b.invoc.target->tag == P_SYMREF)
  87.     addAnEdge(symbolsRead, p->b.invoc.target, p);    
  88.       Sequence_For(q, p->b.invoc.args)
  89.     assert(q->tag == P_ARG);
  90.     q = q->b.arg.exp;
  91.     if (q->tag == P_SYMREF) 
  92.       addAnEdge(symbolsRead, q, p);
  93.       Sequence_Next
  94.       break;
  95.     case P_CONSTDECL:
  96.     case P_VARDECL:
  97.       if (p->b.constdecl.value != NN)
  98.     addAnEdge(symbolsWritten, p->b.constdecl.sym, p);
  99.       break;
  100.     case P_PARAM:
  101.       if (p->b.param.sym->b.symdef.symbol->itsKind == ST_Param)
  102.     addAnEdge(symbolsWritten, p->b.param.sym, p);
  103.       break;
  104.     case P_UNARYEXP:
  105.       if (p->b.unaryexp.exp->tag == P_SYMREF)
  106.     addAnEdge(symbolsWritten, p->b.unaryexp.exp, p);
  107.       break;
  108.     case P_EXP:
  109.       if (p->b.exp.left->tag == P_SYMREF)
  110.     addAnEdge(symbolsWritten, p->b.exp.left, p);
  111.       if (p->b.exp.right->tag == P_SYMREF)
  112.     addAnEdge(symbolsWritten, p->b.exp.right, p);
  113.       break;
  114.     case P_ATLIT:
  115.     case P_OBLIT:
  116.       Sequence_For(q, p->b.oblit.setq)
  117.     if (q->b.setq.outer->tag == P_SYMREF) {
  118.       addAnEdge(symbolsRead, q->b.setq.outer, p);
  119.     }
  120.     assert(q->b.setq.inner->tag == P_SYMDEF);
  121.     addAnEdge(symbolsWritten, q->b.setq.inner, p);
  122.       Sequence_Next
  123.       addAnEdge(symbolsWritten, p->b.atlit.name, p);
  124.       break;
  125.     case P_IMPORT:
  126.       Sequence_For(q, p->b.import.syms)
  127.     addAnEdge(symbolsWritten, q, p);
  128.       Sequence_Next
  129.       break;
  130.     case P_EXPORT:
  131.       if (p->b.export.path == NN) break;
  132.       Sequence_For(q, p->b.export.syms)
  133.     addAnEdge(symbolsWritten, q, p);
  134.       Sequence_Next
  135.       break;
  136.     
  137.     default:
  138.       break;
  139.   }
  140.   Sequence_For(q, p)
  141.     if ((int)q > 0x200) buildSymbolGraph(q);
  142.   Sequence_Next
  143.   switch (p->tag) {
  144.     case P_OBLIT:
  145.       st = p->b.oblit.name->b.symdef.symbol;
  146.       list = (NodePtr) Map_Lookup(symbolsRead, (int)st);
  147.       if ((int)list == NIL) list = NULL;
  148.       duplicatesSelf = FALSE;
  149.       Sequence_For(q, list)
  150.     if (duplicatesSymbol(q, st)) duplicatesSelf = TRUE;
  151.       Sequence_Next
  152.       p->b.oblit.f.doesNotDuplicateSelf = !duplicatesSelf;
  153.       break;
  154.     case P_ATLIT:
  155.       p->b.atlit.f.doesNotDuplicateSelf = TRUE;
  156.       break;
  157.     default:
  158.       break;
  159.   }
  160. }
  161.  
  162. void initializeGraphs()
  163. {
  164.   symbolsRead = Map_Create();
  165.   symbolsWritten = Map_Create();
  166. }
  167.  
  168. static void findSingleReferences()
  169. {
  170.   Symbol st;
  171.   NodePtr list, q;
  172.   Boolean duplicates;
  173.  
  174.   Map_For(symbolsWritten, st, list)
  175.     if (Sequence_Length(list) == 0) {
  176.       TRACE1(graph, 1, "Symbol %s is never written", ST_SymbolName(st));
  177.     } else if (Sequence_Length(list) == 1) {
  178.       TRACE1(graph, 1, "Symbol %s is written only once", ST_SymbolName(st));
  179.       list = (NodePtr) Map_Lookup(symbolsRead, (int)st);
  180.       if (list == (NodePtr)NIL) list = NULL;
  181.       duplicates = FALSE;
  182.       Sequence_For(q, list)
  183.     if (duplicatesSymbol(q, st)) duplicates = TRUE;
  184.       Sequence_Next
  185.       if (!duplicates) {
  186.     TRACE1(graph, 1, "Symbol %s is single reference", ST_SymbolName(st));
  187.     st->isSingleReference = TRUE;
  188.       } else {
  189.     TRACE1(graph, 1, "Symbol %s is not single reference", ST_SymbolName(st));
  190.       }
  191.     } else {
  192.       TRACE2(graph, 1, "Symbol %s is written %d times", ST_SymbolName(st),
  193.     Sequence_Length(list));
  194.     }
  195.   Map_Next
  196. }
  197.   
  198. void displaySymbolGraph()
  199. {
  200.   Symbol st;
  201.   NodePtr list, q;
  202.   IFTRACE(graph, 3) {
  203.     Map_For(symbolsRead, st, list)
  204.       printf("Symbol %s is read:\n", ST_SymbolName(st));
  205.       Sequence_For(q, list)
  206.     printf("\t\tin %s on line %d\n", tagNames[(int)q->tag], q->lineNumber);
  207.       Sequence_Next
  208.       list = (NodePtr) Map_Lookup(symbolsWritten, (int)st);
  209.       if ((int)list != NIL) {
  210.     printf("\tand written:\n");
  211.     Sequence_For(q, list)
  212.       printf("\t\tin %s on line %d\n", tagNames[(int)q->tag], q->lineNumber);
  213.     Sequence_Next
  214.       } else {
  215.     printf("\tbut never written\n");
  216.       }
  217.     Map_Next
  218.     Map_For(symbolsWritten, st, list)
  219.       if (Map_Lookup(symbolsRead, (int)st) == NIL) {
  220.     printf("Symbol %s is only written:\n", ST_SymbolName(st));
  221.     Sequence_For(q, list)
  222.       printf("\t\tin %s on line %d\n", tagNames[(int)q->tag], q->lineNumber);
  223.     Sequence_Next
  224.       }
  225.     Map_Next
  226.   }
  227. }
  228.  
  229. void doSymbolGraph(p)
  230. NodePtr p;
  231. {
  232.   buildSymbolGraph(p);
  233.   findSingleReferences();
  234.   displaySymbolGraph();
  235. }
  236.